// https://leetcode.cn/problems/interleaving-string/description/

// 算法思路总结：
// 1. 动态规划判断字符串s3是否由s1和s2交错组成
// 2. dp[i][j]表示s1前i个字符和s2前j个字符能否交错组成s3前i+j个字符
// 3. 状态转移：当前字符匹配s1或s2且前序状态为真
// 4. 初始化第一行和第一列的单字符串匹配情况
// 5. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    bool isInterleave(string s1, string s2, string s3) 
    {
        int m = s1.size(), n = s2.size();
        if (m + n != s3.size()) return false;

        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;

        for (int i = 1 ; i <= m ; i++)
        {
            if (s1[i] == s3[i])
            {
                dp[i][0] = true;
            }
            else break;
        }

        for (int j = 1 ; j <= n ; j++)
        {
            if (s2[j] == s3[j])
            {
                dp[0][j] = true;
            }
            else break;
        }        

        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 1 ; j <= n ; j++)
            {
                if (s1[i] == s3[i + j] && dp[i - 1][j] == true)
                    dp[i][j] = true;
                else if (s2[j] == s3[i + j] && dp[i][j - 1] == true)
                    dp[i][j] = true;
            }
        }

        return dp[m][n];
    }
};

int main()
{
    string s11 = "aabcc", s12 = "dbbca", s13 = "aadbbcbcac";
    string s21 = "aabcc", s22 = "dbbca", s23 = "aadbbbaccc";

    Solution sol;

    cout << (sol.isInterleave(s11, s12, s13) == 1 ? "true" : "false") << endl;
    cout << (sol.isInterleave(s21, s22, s23) == 1 ? "true" : "false") << endl;

    return 0;
}